//要求：戳气球最大分数
//dp[i][j] nums[i...j]气球被戳后最大分数
public class BalloonMaxCoins {
}
class BalloonMaxCoinsSolution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] help = new int[n+2];
        for(int i=0;i<n;i++)
            help[i+1] = nums[i];
        help[0] = 1;
        help[n+1] = 1;
        int[][] dp = new int[n+1][n+1];
        for(int i=1;i<=n;i++)//仅戳一个气球
            dp[i][i] = help[i]*help[i-1]*help[i+1];
        for(int j=2;j<=n;j++){
            for(int i=j-1;i>0;i--){
                //最后戳两边气球
                dp[i][j] = Math.max(help[i]*help[i-1]*help[j+1]+dp[i+1][j],help[i-1]*help[j]*help[j+1]+dp[i][j-1]);
                //最后戳中间气球
                for(int k=i+1;k<j;k++){
                    dp[i][j] = Math.max(dp[i][j],help[k]*help[i-1]*help[j+1]+dp[i][k-1]+dp[k+1][j]);
                }
            }
        }
        return dp[1][n];
    }
}